
%-----------------------------------------------------
%-----------------------------------------------------
% Relatorio Agents-Language
% Caio Arce Nishibe
%-----------------------------------------------------
%-----------------------------------------------------

\documentclass[
%-------------------------
% opções da classe memoir
%-------------------------
12pt, 				%tamanho da fonte
openright, 		%capítulos começam em página ímpar
oneside, 			%para impressão somente em anverso (oposto a twoside)
a4paper, 			%tamanho do papel
%-------------------------
%opções da classe abntex2
%-------------------------
chapter=TITLE,			%títulos de capítulos em letras maiúsculas
section=TITLE, 			%títulos de seções em letras maiúsculas
subsection=TITLE,		%títulos de subseções convertidos em letras maiúsculas
subsubsection=TITLE,%títulos de subsubselções em letras maiúsculas
%-------------------------
%opções do pacote babel
%-------------------------
english,		%idioma adicional para hifenização
brazil			%o último idioma é o principal do documento
]{abntex2}

%-------------------------
% PACOTES
%-------------------------

%pacotes básicos
\usepackage{lmodern}					%usa fonte Latin Modern
\usepackage[T1]{fontenc}			%seleção de códigos de fonte
\usepackage[utf8]{inputenc}		%codificação do documento (conversão automática de acentos)
\usepackage{indentfirst}			%identa o primeiro parágrafo de cada seção
\usepackage{color}						%controle de cores
\usepackage{graphics}					%inclusão de gráficos
\usepackage{microtype}				%para melhorias de justificação

%pacotes adicionais
\usepackage[brazilian, hyperpageref]{backref}		%páginas com as citações na bibl
\usepackage[alf]{abntex2cite}										%citações padrão abnt
\usepackage{tikz}																%desenhos
\usepackage{listings}




\usetikzlibrary{shapes,arrows, positioning, decorations.markings, intersections, through, fit}
% Define block styles
\tikzstyle{block} = [rectangle, draw, text width=7em, text centered, rounded corners, minimum height=4em]
\tikzstyle{cloud} = [draw, ellipse, node distance=3.5cm, minimum height=4em, text width=5em]
\tikzstyle{line} = [draw, -latex']

%customizações do abntex2 para UTFPR
\usepackage{UTFPR}

%-------------------------
% CONFIGURAÇÔES DE PACOTES
%-------------------------

% Altera o nome padrão do rótulo usado no comando \autoref{}
\renewcommand{\lstlistingname}{Código}

% Altera o rótulo a ser usando no elemento pré-textual "Lista de código"
\renewcommand{\lstlistlistingname}{Lista de códigos}

% Configura a ``Lista de Códigos'' conforme as regras da ABNT (para abnTeX2)
\begingroup\makeatletter
\let\newcounter\@gobble\let\setcounter\@gobbletwo
  \globaldefs\@ne \let\c@loldepth\@ne
  \newlistof{listings}{lol}{\lstlistlistingname}
  \newlistentry{lstlisting}{lol}{0}
\endgroup

\renewcommand{\cftlstlistingaftersnum}{\hfill--\hfill}

\let\oldlstlistoflistings\lstlistoflistings
\renewcommand{\lstlistoflistings}{%
   \begingroup%
   \let\oldnumberline\numberline%
   \renewcommand{\numberline}{\lstlistingname\space\oldnumberline}%
   \oldlstlistoflistings%
   \endgroup}

%Configurações do pacote backref
\renewcommand{\backrefpagesname}{Citado na(s) página(s):~}
\renewcommand{\backref}{}
\renewcommand*{\backrefalt}[4]{
	\ifcase #1 %
		Nenhuma citação no texto.
	\or
		Citado na página #2.%
\else
		Citado #1 vezes nas páginas #2.%
	\fi}
	
	\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
\definecolor{light-gray}{gray}{0.8}
	\lstset{ %
  backgroundcolor=\color{light-gray},   % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
  basicstyle=\footnotesize,        % the size of the fonts that are used for the code
  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  breaklines=true,                 % sets automatic line breaking
  %captionpos=b,                    % sets the caption-position to bottom
  commentstyle=\color{mygreen},    % comment style
  deletekeywords={...},            % if you want to delete keywords from the given language
  escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
  extendedchars=true,              % lets you use non-ASCII characters; for 8-bits encodings only, does not work with UTF-8
  frame=single,                    % adds a frame around the code
  keepspaces=true,                 % keeps spaces in text, useful for keeping indentation of code (possibly needs columns=flexible)
  keywordstyle=\color{blue},       % keyword style
  language=C++,                 % the language of the code
  morekeywords={*,...},            % if you want to add more keywords to the set
  numbers=left,                    % where to put the line-numbers; possible values are (none, left, right)
  numbersep=5pt,                   % how far the line-numbers are from the code
  numberstyle=\tiny\color{mygray}, % the style that is used for the line-numbers
  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
  showspaces=false,                % show spaces everywhere adding particular underscores; it overrides 'showstringspaces'
  showstringspaces=false,          % underline spaces within strings only
  showtabs=false,                  % show tabs within strings adding particular underscores
  stepnumber=2,                    % the step between two line-numbers. If it's 1, each line will be numbered
  stringstyle=\color{mymauve},     % string literal style
  tabsize=2,                       % sets default tabsize to 2 spaces
  %title=\lstname                   % show the filename of files included with \lstinputlisting; also try caption instead of title
}
	
%-------------------------
% Dados para CAPA e FOLHA DE ROSTO
%-------------------------

\titulo{\emph{AGENTS-LANGUAGE}: UMA LINGUAGEM DE PROGRAMAÇÃO PARA ROBÔS}
\author{CAIO ARCE NISHIBE}
\local{CURITIBA}
\data{2014}
\instituicao{
	UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ
	\\
	PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E INFORMÁTICA INDUSTRIAL	
}
\tipotrabalho{RELATÓRIO}
\preambulo{Relatório apresentado à disciplina de Linguagens e Compiladores do Programa de Pós-Graduação em Computação Aplicada da Universidade Tecnológica Federal do Paraná.}
\orientador[Professor: ]{Dr. João Alberto Fabro}


%-------------------------
% Configurações do pdf
%-------------------------

% alterando o aspecto da cor azul
\definecolor{blue}{RGB}{41,5,195}

% informações do PDF
\makeatletter
\hypersetup{
    %pagebackref=true,
		pdftitle={\@title}, 
		pdfauthor={\@author},
    	pdfsubject={\imprimirpreambulo},
	    pdfcreator={LaTeX with abnTeX2},
		pdfkeywords={utfpr}{cpgei}, 
		colorlinks=true,       		% false: boxed links; true: colored links
    	linkcolor=blue,          	% color of internal links
    	citecolor=blue,        		% color of links to bibliography
    	filecolor=magenta,      		% color of file links
		urlcolor=blue,
		bookmarksdepth=4
}
\makeatother

%-------------------------
% Espaçamentos entre linhas e parágrafos
%-------------------------

% O tamanho do parágrafo é dado por:
\setlength{\parindent}{1.3cm}

% Controle do espaçamento entre um parágrafo e outro:
\setlength{\parskip}{0.2cm} 


\begin{document}

% Retira espaço extra obsoleto entre as frases.
\frenchspacing 

%------------------------------
% Elementos Pré Textuais
%------------------------------
\pretextual
%capa
\imprimircapa

%folha de rosto
\imprimirfolhaderosto

%resumo
\begin{resumo}
\emph{Agents Language} é uma linguagem de programação muito simples que permite controlar robôs. Este relatório descreve todo o processo de construção desta linguagem, desde a especificação de sua gramática, passando pela implementação do compilador e por fim a integração com o simulador de robôs V-REP.

\vspace{\onelineskip}

\noindent
\textbf{Palavras-chave}: compilador. linguagem de programação. robô. Flex. Bison.
\end{resumo}

%abstract
\begin{resumo}[Abstract]
\begin{otherlanguage*}{english}
Agents Language is a very simple programming language that allows users to control robots. This report describes the entire process of building this language, from the specification of its grammar, through the implementation of the compiler and finally the integration with the robots simulator V-REP.

\vspace{\onelineskip}

\noindent
\textbf{Keywords}: compiler. programming language. robot. Flex. Bison.
\end{otherlanguage*}
\end{resumo}

%lista de figuras
\pdfbookmark[0]{\listfigurename}{lof}
\listoffigures*
\cleardoublepage
%lista de tabelas
%\pdfbookmark[0]{\listtablename}{lot}
%\listoftables*
%\cleardoublepage
%lista de abreviaturas e siglas
\begin{siglas}
	\item[API] \emph{Application Programming Interface} (Interface de Programação de Aplicações)
	\item[AST] \emph{Abstract Sintax Tree} (Árvore Sintática Abstrata)
	\item[IDE] \emph{Integrated Development Environment} (Ambiente Integrado de Desenvolvimento)
	\item[V-REP] \emph{Virtual Robot Experimentation Platform}
	
\end{siglas}

% ---
% inserir lista de listings
% ---
\pdfbookmark[0]{\lstlistlistingname}{lol}
\begin{KeepFromToc}
\lstlistoflistings
\end{KeepFromToc}
\cleardoublepage
% ---

%sumário
\pdfbookmark[0]{\contentsname}{toc}
\tableofcontents*
\cleardoublepage


%------------------------------
% Elementos Textuais
%------------------------------
\textual

%Introdução
\chapter{Introdução}

Este capítulo apresenta em que contexto está inserido este trabalho, bem como seus objetivos, justificativa, metodologia e de que forma está estruturado este documento.

\section{Contexto}

Este trabalho está inserido em uma disciplina de Linguagens e Compiladores do Programa de Pós-Graduação em Computação Aplicada da Universidade Tecnológica Federal do Paraná. 

Após algumas aulas expositivas para que fosse construída uma base teórica mínima necessária, decidiu-se que adotar uma abordagem prática produziria melhores resultados. Foi proposto então, a criação de um compilador para uma linguagem de programação nova, dedicada a controlar robôs. Esta linguagem, chamada de \emph{Agents Language}, seria simples, com propósito didático, mas com a possibilidade de expansão de funcionalidades.

\section{Objetivos}
\subsection{Objetivo Geral}
O objetivo geral deste trabalho é conceber uma linguagem de programação para robôs.

\subsection{Objetivos Específicos}
Os objetivos específicos deste trabalho são:

\begin{itemize}
	\item Aprofundar conhecimentos sobre a teoria de Linguagens e Compiladores.
	\item Especificar uma gramática para a construção do compilador.
	\item Implementar o analisador léxico.
	\item Implementar o analisador sintático.
	\item Implementar o analisador semântico.
	\item Implementar gerador de código C++.
	\item Integrar com o simulador V-REP.
\end{itemize}

\section{Justificativa}

Para que haja uma consolidação da teoria sobre linguagens e compiladores aprendida em sala de aula, é necessário colocar em prática todo o conhecimento obtido. Sendo assim, um trabalho como este se faz de extrema importância. 

\section{Metodologia}

Para alcançar os objetivos propostos, este trabalho se desenvolveu nas etapas descritas a seguir:

\begin{itemize}
	\item revisão da literatura e levantamento de material teórico necessário.
	\item especificação em grupo de uma gramática para a construção do compilador.
	\item implementação do analisador léxico.
	\item implementação do analisador sintático.
	\item implementação do analisador semântico.
	\item implementação do gerador de código C++.
	\item integração com o simulador V-REP.
	\item testes de \emph{software}.
	\item análise dos resultados e conclusões.
\end{itemize}

\section{Estrutura do Documento}

O Capítulo 2 apresenta os conceitos presentes na literatura que serviram como base na análise e justificativa das decisões deste trabalho. Neste capítulo há uma breve introdução à teoria de linguagens e compiladores e aos demais conceitos necessários para a realização deste.

O Capítulo 3 contém a especificação da \emph{Agents Language}. São apresentadas a especificação da gramática, bem como de todo o \emph{software} produzido.

O Capítulo 4 descreve como este trabalho foi desenvolvido, apresentando todos os detalhes técnicos.

O Capítulo 5 apresenta os resultados obtidos.

O Capítulo 6 contém as conclusões e sugestões para trabalhos futuros.


%Fundamentação Teórica
\chapter{Fundamentação Teórica}

Este capítulo apresenta uma breve introdução à teoria de linguagens e compiladores e aos demais conceitos necessários para o desenvolvimento deste trabalho.

\section{Gramáticas e Linguagens Livres do Contexto}

As linguagens livres do contexto têm uma notação natural, recursiva, denominada gramática livre de contexto \cite{john}. As gramáticas livres do contexto são um método poderoso para especificar linguagens pois têm capacidade de descrever características que possuam uma estrutura recursiva \cite{sipser}. Tais gramáticas são utilizadas na especificação e compilação de linguagens de programação desde a década de 1960 \cite{john}. Em geral, o projeto de um compilador ou interpretador para uma linguagem de programação começa pela especificação de uma gramática \cite {sipser}. 

Segundo \citeonline{john}, há quatro componentes importantes em uma descrição gramatical de uma linguagem:

\begin{itemize}
	\item Existe um conjunto finito de símbolos que formam as sentenças da linguagem que está sendo definida. Esse alfabeto é chamado de terminais ou símbolos terminais.
	\item Existe um conjunto finito de variáveis, também chamadas de não terminais ou categorias sintáticas. Cada variável representa uma linguagem, ou seja um conjunto de sentenças.
	\item Uma das variáveis representa a linguagem que está sendo definida. Ela é chamada de símbolo de início. As demais variáveis representam classes auxiliares de sentenças que são utilizadas para completar a definição da linguagem do símbolo de início.
	\item Existe um conjunto finito de produções ou regras que representam a definição recursiva de uma linguagem.
\end{itemize}


\citeonline{john} afirmam ainda que, cada produção é formada por:
\begin{itemize}
	\item Uma variável (cabeça da produção) que está sendo definida pela produção.
	\item O símbolo de produção ($\rightarrow$).
	\item Uma sentença de zero ou mais terminais e variáveis (corpo da produção).
\end{itemize}


Para \citeonline{sipser}, uma gramática livre de contexto pode ser definida formalmente como um 4-upla $(V,\sum,R,S)$, onde:

\begin{itemize}
	\item $V$ é um conjunto finito denominado variáveis.
	\item $\sum$ é um conjunto finito, disjunto de $V$, denominado terminais.
	\item $R$ é um conjunto finito de regras, com cada regra sendo uma variável e uma cadeia de variáveis e terminais.
	\item $S \in V$ é a variável de início.
\end{itemize}

\section{Compiladores}

A maioria dos computadores é projetada para executar comandos extremamente simples, em linguagem de máquina, de forma muito rápida. Um programa de computador é a combinação destes comandos simples. Devido à alta complexidade de programar em linguagem de máquina, a maior parte dos programas são feitos em linguagens de programação de alto nível. Entretanto, este tipo de linguagem pode ser muito diferente da linguagem de máquina que o computador executa \cite{torben}.

De acordo com \citeonline{torben}, o compilador é aquele que traduz um programa escrito em uma linguagem de programação de alto nível para uma linguagem de mais baixo nível.

Segundo \citeonline{william}, o processo de compilação (\autoref{proc-comp}) pode ser dividido em duas etapas principais: análise e síntese. A análise é responsável pela descoberta da estrutura e as primitivas do programa de entrada, além da determinação de seu significado. A síntese cria um programa de saída na linguagem alvo equivalente ao programa de entrada.

A etapa de análise pode ser dividida em duas tarefas principais, a análise estrutural que determina a estrutura estática do programa de entrada, e a análise semântica que estabelece informações adicionais e verifica a consistência. A análise estrutural é formada por duas sub-tarefas: a análise léxica trata dos símbolos básicos do programa de entrada e é descrita por autômatos finitos; a análise sintática trata da estrutura estática do programa e é descrita por autômatos de pilha \cite{william}.

A etapa de síntese é composto por duas sub-etapas: geração de código e montagem. A geração de código transforma a abstração do programa de entrada, produzida pela análise, em um programa equivlente na linguagem alvo. A montagem converte as instruções da linguagem alvo em um formato de saída apropriado \cite{william}.


\begin{figure}[!h]
\centering
\begin{tikzpicture}[auto, node distance = 4cm, thick, >=stealth']

\tikzstyle{block} = [draw=black, text width = 7em, rounded corners, text centered, minimum height = 3em]

	
	\node[circle, fill, draw, inner sep=+0pt, minimum size=+5pt, name=input](input){};
	\node[above of=input, node distance = 0.5cm]{entrada};
	\node[block, right of=input](lex){Análise Léxica};
	\node[block, right of=lex](sint){Análise Sintática};
	\node[block, right of=sint](sem){Análise Semântica};
	\node[block, below of=sem](cod){Gerador de Código};
	\node[block, left of=cod](mont){Montagem};
	\node[circle, fill, draw, inner sep=+0pt, minimum size=+5pt, name=output, left of=mont](output){};
	\node[above of=output, node distance = 0.5cm]{saída};
	\node[above of=lex, node distance = 1.5cm](A){Análise Estrutural};
	\node[above of=A, node distance = 1.5cm](B){\textbf{ANÁLISE}};
	\node[above of=mont, node distance = 1.5cm](C){\textbf{SÍNTESE}};
	\node[fit=(A)(lex)(sint), dotted,draw,inner sep=0.45cm,
	](estr){};
	\node[fit=(B)(lex)(sint)(sem), dashed,draw,inner sep=0.8cm,
	](estr){};
	\node[fit=(C)(mont)(cod), dashed,draw,inner sep=0.45cm,
	](estr){};
	
	
	\path[line](input) -> (lex);
	\path[line](lex) -> (sint);
	\path[line](sint) -> (sem);
	\path[line](sem) -> (cod);
	\path[line](cod) -> (mont);
	\path[line](mont) -> (output);
	
\end{tikzpicture}\caption{Etapas do Processo de Compilação}%
\label{proc-comp}%
\end{figure}

\section{Flex e Bison}

Segundo \citeonline{levine}, Flex e Bison são os substitutos do lex e yacc, ambos desenvolvidos na década de 1970 por \emph{Bell Laboratories}. Eles foram originalmente criados para construir compiladores, mas hoje em dia são utilizados em diversas aplicações para tratar entradas estruturadas.

De forma geral, o analisador léxico (Flex) divide a entrada em pequenos pedaços com algum significado, chamados de \emph{tokens}, e o analisador sintático (Bison) verifica como os \emph{tokens} se relacionam entre si \cite{levine}.


Analisadores léxicos (\emph{scanners}) procuram por padrões de caracteres na entrada. Uma maneira de especificar esses padrões é através de expressões regulares. Um analisador léxico Flex é formado por uma lista de expressões regulares juntamente com instruções sobre o que fazer quando a entrada corresponde a alguma delas \cite{levine}.

Analisadores sintáticos (\emph{parsers}) verificam as relações entre os \emph{tokens} da entrada. Uma maneira de mostrar essas relações é através de uma árvore sintática, e é desta forma que o Bison faz a análise \cite{levine}.


\chapter{Especificação}

Neste capítulo serão apresentados a especificação da gramática da linguagem proposta, bem como as especificações de \emph{software} do compilador.

\section{Regras Gramaticais da \emph{Agents Language}}

A seguir serão descritas as regras gramaticais da \emph{Agents Language} que foram implementadas nesta versão:

\begin{enumerate}
	\item PROGRAM ::= NAME DECL RULES
	\item NAME ::= \textbf{<nome>} IDENTIFIER \textbf{</nome>} | \\ 
	\textbf{<nome>} IDENTIFIER \textbf{</nome><versão>} NUMBER \textbf{</versão>}
	\item DECL ::= \textbf{<variavel>} IDENTIFIER NUMBER \textbf{</variavel>} | \\
	 \textbf{<variavel>} IDENTIFIER NUMBER \textbf{</variavel>} DECL
	\item RULES ::= \textbf{<regras>} RULES\_SET \textbf{</regras>}
	\item RULES\_SET ::= \textbf{<regra>} RULE \textbf{</regra>} | \\
	\textbf{<regra>} RULE \textbf{</regra>} RULE\_SET
	\item RULE ::= ACTION | \\
	\textbf{<se>} CONDITION \textbf{<entao>} ACTION \textbf{</se>} | \\
	\textbf{<se>} CONDITION \textbf{<entao>} ACTION \textbf{<senao>} ACTION \textbf{</se>} 
	\item CONDITION ::= \textbf{<condicao>} INTERNAL\_CONDITION \textbf{</condicao>}
	\item INTERNAL\_CONDITION ::= ARITH\_EXPR COMP\_OP ARITH\_EXPR | \\
	NOT INTERNAL\_CONDITION | \\
	INTERNAL\_CONDITION AND INTERNAL\_CONDITION | \\
	INTERNAL\_CONDITION OR INTERNAL\_CONDITION | \\
	(INTERNAL\_CONDITION)
	\item ARITH\_EXPR ::= ARITH\_EXPR ARITH\_OP ARITH\_EXPR | \\
	NUMBER | \\
	IDENTIFIER | \\
	(ARITH\_EXPR)
	\item COMP\_OP ::= ``<'' | ``<='' | ``>'' | ``>='' | ``<>'' | ``=='' |
	\item ARITH\_OP ::= ``$+$'' | ``$-$'' | ``$*$'' | ``$/$'' 
	\item ACTION ::= \textbf{<comandos>} COMMANDS \textbf{</comandos>}
	\item COMMANDS ::= \textbf{<comando>} CMD \textbf{</comando>} | \\
	\textbf{<comando>} CMD \textbf{</comando>} COMMANDS
	\item CMD ::= IDENTIFIER $\leftarrow$ NUMBER | \\
	IDENTIFIER $\leftarrow$ ARITH\_EXPR | \\
	\textbf{<leia\_sensor>} IDENTIFIER \textbf{</leia\_sensor>} | \\
		\textbf{<mensagem>} NAME IDENTIFIER \textbf{</mensagem>} | \\	
	\textbf{<escreva\_atuador>} IDENTIFIER NUMBER \textbf{</escreva\_atuador>}
	
	\item IDENTIFIER ::= CHARACTER STRING
	\item STRING ::= CHARACTER STRING | \\ \_IDENT2 | DIGIT STRING | $\varepsilon$
	\item IDENT2 ::= CHARACTER STRING | \\DIGIT STRING
	\item CHARACTER ::= A | ... | z
	\item DIGIT ::= 0 | ... | 9
\end{enumerate}


\section{Especificação de \emph{Software}}

Esta seção detalhará a especificação de \emph{software} do compilador e da biblioteca para comunicação entre robôs.


\subsection{Diagrama de Classes}
O diagrama de classes é aquele que apresenta a estrutura do sistema que está sendo modelado no nível de classes e interfaces, além de mostrar seus atributos, restrições, e relações \cite{uml}. A \autoref{class-diagram} apresenta o diagrama de classes das estruturas utilizadas no compilador.

\begin{figure} [!h]%
\centering
\includegraphics[width=0.8\columnwidth]{class-diagram}%
\caption{Diagrama de Classes do Compilador}%
\label{class-diagram}%
\end{figure}

A enumeração \texttt{Kind} contém todos os tipos possíveis de nós da AST. A enumeração \texttt{Type} contém todos os tipos possíveis de valores que podem ser armazenados em um nó da AST. A enumeração \texttt{LogicOp} contém os operadores lógicos. A enumeração \texttt{ArithOp} contém os operadores aritméticos disponíveis. E por fim, a enumeração \texttt{CompOp} contém os operadores de comparação. 

A classe \texttt{Value} armazena valores pertinentes do nó. É possível armazenar números, \emph{strings}, operadores de comparação, operadores lógicos e operadores aritméticos. Além da construtora e destrutora, existem métodos para atribuir um valor (\texttt{SetValueFromString}, \texttt{SetValueFrom Number}, \texttt{SetValueFromOpComp}, \texttt{SetValueFromOpLogic}, \\* \texttt{SetValueFromOpArit}), obter o valor armazenado (\texttt{GetValue}) e imprimir no console o valor armazenado, dado um tipo (\texttt{PrintValue}). 


A classe \texttt{ASTNode}, representa um nó da AST. Nela é possível armazenar o nome do nó, seu tipo, o tipo do valor armazenado, um valor, o número da linha de código em que foi encontrado tal valor, um ponteiro para o nó pai, um ponteiro para os nós filhos e um ponteiro para os nós irmãos. Além das construtoras e destrutora, existem os métodos para adicionar um irmão (\texttt{AddSibling}), adicionar um filho (\texttt{AddChild}) e o método para aceitar o nó através de um \texttt{IVisitor} (\texttt{Accept}).

A classe \texttt{AbstractSyntaxTree}, representa uma Árvore Sintática Abstrata. Ela armazena o nó raíz da árvore. Além das construtoras e destutora, existe o método \texttt{PrintAST} que imprime no console toda a estrutura da árvore. 

A classe \texttt{Symbol} armazena o nome do símbolo, o tipo do valor armazenado, um valor, à quem pertence esse símbolo (escopo), a linha de código em que foi declarado este símbolo e um ponteiro para o próximo símbolo. Nesta classe existem só as construtoras e a destrutora.

A classe \texttt{SymbolTable} representa uma tabela de símbolos. Ela armazena o ponteiro para o primeiro elemento da lista. Além da constutora e destrutora, existem os métodos de inserção de símbolo na lista (\texttt{InsertSymbol})e de pesquisa na lista (\texttt{LookupSymbol}).

A interface \texttt{IVisitor} descreve os métodos que devem ser implementados pelas classes que realizam esta interface. Tais métodos são chamados durante a visita de cada nó da AST. Através desta interface podem ser implementados facilmente novos geradores de código em outras linguagens e analisadores de tipo e até mesmo um analisador semântico.

A classe \texttt{CodeGenerator} implementa a interface \texttt{IVisitor}. Esta classe gera código C++, em um arquivo de saída, a partir da AST.

A classe \texttt{ASTChecker} também implementa a interface \texttt{IVisitor}. Esta classe verifica inconsistências na AST, e monta uma tabela de símbolos.

A \autoref{message-class-diagram} apresenta o diagrama de classes da biblioteca criada para troca de mensagens entre os agentes.


\begin{figure}[!h]%
\centering
\includegraphics[width=0.6\columnwidth]{message-class-diagram}%
\caption{Diagrama de Classes da Biblioteca de Mensagens}%
\label{message-class-diagram}%
\end{figure}

A enumeração \texttt{MessageType} contém os tipos de mensagens que podem ser trocadas. Cada tipo será aprensentado a seguir:
\begin{itemize}
	\item \texttt{ANY\_MESSAGE\_FOR\_ME}: com este tipo de mensagem o agente pode perguntar ao servidor se existe alguma mensagem endereçada a ele.
	\item \texttt{NO\_MESSAGES\_FOR\_YOU}: com este tipo de mensagem o servidor responde ao agente que não existem mensagens endereçadas a ele.
	\item \texttt{SEND\_INFO}: este tipo de mensagem indica que estão sendo enviadas informações (valores de variáveis) a outro agente.
	\item \texttt{REQUEST\_INFO}: este tipo de mensagem indica que estão sendo requisitadas informações (valores de variáveis) de outro agente.
\end{itemize}

A classe \texttt{MessageHeader} representa o cabeçalho da mensagem. Possui tamanho fixo para facilitar o protocolo de troca de mensagens. Nos primeiros quatro \emph{bytes} contém o tamanho da mensagem e no quinto \emph{byte} o tipo da mesma.

A classe \texttt{Messsage} representa uma mensagem. Contém um cabeçalho e efetivamente a mensagem em forma de uma \emph{string} que deve ser enviada.

A \autoref{message-server-class-diagram} apresenta o diagrama de classes do servidor de mensagens.


\begin{figure}[!h]%
\centering
\includegraphics[width=0.6\columnwidth]{message-server-class-diagram}%
\caption{Diagrama de Classes do Servidor Mensagens}%
\label{message-server-class-diagram}%
\end{figure}

A classe \texttt{Session} representa uma sessão no servidor de mensagens. Quando uma mensagem é recebida, uma sessão é criada.

A classe \texttt{MessageServer} representa o servidor de mensagens. Contém uma tabela para armazenar as mensagens recebidas.

Maiores detalhes sobre as classes apresentadas podem ser encontrados na documentação que acompanha este relatório.

\chapter{Desenvolvimento do Sistema}

Este capítulo descreve todas as etapas que foram realizadas neste trabalho, desde a implementação do compilador até a integração com o simulador V-REP.

\section{Ambiente de desenvolvimento}

Todo o densenvolvimento deste projeto foi feito utilizando um computador com sistema operacional \emph{Microsoft Windows 8.1}. Entretanto, nenhuma dependência de tal sistema operacional foi utilizada. Portanto, para portar todo o conteúdo aqui produzido para outros sistemas operacionais é uma tarefa relativamente fácil.

Para codificação foi utilizada a IDE \emph{Visual Studio 2013} e as linguagens de programação C e C++.


\section{Flex \& Bison}

Originalmente as ferramentas Flex e Bison foram concebidas para ambientes \emph{Linux}. Portanto, neste projeto foi utilizado um porte para \emph{Windows} chamado \emph{Win flex-bison}.

Este porte é bastante estável e constantemente atualizado para novas versões do Flex e Bison. Outra grande vantagem é que ele disponibiliza arquivos de \emph{custom-build-rules}
para o \emph{Visual Studio}, facilitando assim a compilação, que fica totalmente transparente para o programador.

\section{Compilador}

Após especificada a gramática, o primeiro passo foi escrever o \emph{parser} utilizando o Bison. Um arquivo \texttt{.y} possui três partes. Na primeira parte são definidos os \emph{includes}, as opções e todos os \emph{tokens} (\autoref{first-section}) . Na segunda parte são definidas as regras gramaticais (\autoref{second-section}). E por fim, na terceira parte está a função \emph{main} (\autoref{third-section}) e demais funções auxiliares.

Utilizou-se a biblioteca \emph{Boost} para auxiliar a implementação das opções do compilador. Foram implementadas as opções:

\begin{itemize}
	\item \texttt{-i/-input}: que indica o arquivo de entrada para compilação. Esta opção é obrigatória.
	\item \texttt{-o/-output}: que indica o arquivo de saída \texttt{.cpp}. Esta opção é obrigatória.
	\item \texttt{-h/-help}: que mostra todas as opções disponíveis.
	\item \texttt{-v/-verbose}: que imprime a AST, além de mostrar os passos da compilação.
\end{itemize}


\begin{lstlisting}[frame=single, language=C++, framerule=0pt, caption={Trecho da primeira seção do arquivo .y contendo a descrição dos \emph{tokens}}, label=first-section]
%token <number> NUMBER
%token <string> IDENTIFIER
%token <arithOp> ARITH_OP
%token <string> PARENTHESES_START
%token <string> PARENTHESES_END
%token <compOp> COMP_OP
%token <logicOp> LOGIC_OP
%token <string> ASSIGNMENT_OP
\end{lstlisting}

\begin{lstlisting}[frame=single, framerule=0pt, caption={Exemplo de regra gramatical}, label=second-section]
program:
	name decl rules
	{		
		ASTNode *node = new ASTNode("program", PROGRAM, VOID, yylloc.last_line);
		
		node->AddChild($1); //name
		node->AddChild($2); //decl
		node->AddChild($3); //rules

		$$ = node;
		ast->ast = node;
	};
\end{lstlisting}

\begin{lstlisting}[frame=single, framerule=0pt, caption={Exemplo de função \emph{main}}, label=third-section]
int main (int argc, char **argv)
{
	bool verbose = false;
	std::string inputPath;
	std::string outputPath;	
	try
	{
		std::string appName = "Agents Language Compiler";		
		namespace po = boost::program_options;
		po::options_description desc("Options");
		desc.add_options()
			("help,h", "print help messages")
			("verbose,v", "print debug symbols")
			("input,i", po::value<std::string>()->required(),"input file to be compiled")
			("output,o", po::value<std::string>()->required(),"output c++ file");

		po::variables_map vm;
		try
		{
			po::store(po::command_line_parser(argc,argv).options(desc).run(), vm);
			//--help
			if(vm.count("help"))
			{
				std::cout << "-- Agents Language Compiler --" << endl
						  << desc << endl;							
			}
			po::notify(vm);
		}
		catch(boost::program_options::required_option& e)
		{
			std::cerr << "ERROR: " << e.what() << std::endl;
			return -1;
		}
		catch(boost::program_options::error& e)
		{
			std::cerr << "ERROR: " << e.what() << std::endl; 
			return -1;
		}		
		//--verbose
		if(vm.count("verbose"))
		{
			verbose = true;			
		}
		//--input
		inputPath = vm["input"].as<std::string>();		
		//--output
		outputPath = vm["output"].as<std::string>();
		yyin = NULL;	
		yyin = fopen(inputPath.c_str(), "r");
		if(yyin == NULL)
		{
			cout << "Unable to read input file!" <<endl;
			return -1;
		}
		else
		{
			if(verbose)
				cout << "Input file loaded." <<endl;
		}
		//initialize ast
		ast = new AbstractSyntaxTree();	
		//do parse
		if(verbose)
			cout << "Parsing file" <<endl;
		yyparse(); 
		//print ast
		if(verbose)
			ast->PrintAST();
		//initialize symbol table
		symbolTable = new SymbolTable();
		//cheking AST semantics and filling symbol table
		IVisitor *checker = NULL;
		checker = new ASTChecker(symbolTable);
		if(verbose)
			cout << "Checking AST" <<endl;
		ast->ast->Accept(checker);
		if(checker != NULL)
			delete checker;
		//genetaring output C file
		IVisitor *cGen = NULL;
		cGen = new CodeGenerator(outputPath);
		if(verbose)
			cout << "Generating code" << endl;
		ast->ast->Accept(cGen);
		if(verbose)
			cout << "Code generated successfully!" <<endl;
		if(cGen != NULL)
			delete cGen;	
		if(ast != NULL)
			delete ast;		
		if(symbolTable != NULL)
			delete symbolTable;	

		return 0;
	}
	catch(std::exception& e)
	{
		std::cerr << "Unhandled Exception: " << e.what() << std::endl;
		return -1;
	}
}
\end{lstlisting}

Sabendo quais \emph{tokens} precisavam ser identificados, foi possível implementar o \emph{scanner} utilizando Flex. O arquivo \texttt{.l} também possui três partes como o arquivo \texttt{.y}. Na primeira seção são definidos os \emph{includes} e as opções do Flex (\autoref{f-section-flex}). Na segunda seção são definidos os \emph{tokens} e quais ações devem ser executadas quando são encontrados (\autoref{s-section-flex}). E na terceira seção, pode ser definida a função \emph{main}, porém neste caso ela está vazia, visto que quem possui tal função é o \emph{parser}.

\begin{lstlisting}[frame=single, framerule=0pt, caption={Trecho da primeira seção do arquivo \texttt{.l} onde são definidas as opções do Flex}, label=f-section-flex]
%option yylineno
%option bison-bridge
%option bison-locations
%option noyywrap
%option nounput
\end{lstlisting}

\begin{lstlisting}[frame=single, framerule=0pt, caption={Reconhecimento do \emph{token} número}, label=s-section-flex]
([\+-])?[0-9]+\.[0-9]+				{
																update_location; 
																yylval->number = atof(yytext);
																return NUMBER;
															}
\end{lstlisting}


Com o \emph{parser} e o \emph{scanner} prontos, foi possível obter a AST. O próximo passo foi percorrer a árvore procurando por inconsistências semânticas,  fazendo uma checagem de tipos e montando a tabela de símbolos.

A última etapa foi implementar a geração de código, onde o gerador de código C++ percorre a AST, visitando cada nó e gerando o código correspondente na linguagem C++. Sendo assim, este compilador recebe como entrada um arquivo na linguagem \emph{Agents Language}, e gera como saída um arquivo \texttt{.cpp}, que deve ser adicionado a um projeto C++ e compilado.

\section{Servidor de Mensagens}

Para que os agentes pudessem se comunicar, foi implementado um servidor de mensagens. A cada iteração da simulação o agente envia uma mensagem perguntando ao servidor se existe alguma mensagem endereçada à ele. Se não existir, o servidor responde que não existem mensagens. Caso contrário, o servidor repassa a mensagem para o agente. Existem muitas maneiras de implementar tal servidor, mas por uma questão de simplicidade, este foi implementado utilizando \emph{sockets}, que foram abstraídos através da biblioteca \emph{Boost}, e uma arquitetura cliente-servidor simples.

A utilização da biblioteca \emph{Boost} fez-se necessário pois esta possui uma implementação alto nível de \emph{sockets} e totalmente independente de sistema operacional. Sendo assim, para que este projeto seja compilado em outro sistema operacional, basta trocar a biblioteca no momento da compilação, sem precisar alterar o código fonte.

\section{Integração com Simulador V-REP}

O simulador V-REP possui uma API que permite o controle dos robôs por um programa C++. Esta API foi utilizada para exportar algumas funções básicas que permitissem o controle de um robô seguidor de linha.

Para validação do compilador, inicialmente foi construída uma cena no simulador com apenas um robô seguidor de linha. Tal robô possuía apenas três sensores de visão acoplados na parte da frente, alinhados.

Após, foi introduzido mais um robô seguidor de linha na cena, e um semáforo. Os dois robôs, agora dotados de um sensor de proximidade, trocavam mensagens com o semáforo a fim de saber se este estava aberto ou fechado.

\chapter{Resultados}

Este capítulo apresenta os resultados obtidos, detalhando o estado atual do compilador e da integração com o simulador V-REP.

\section{Compilador}

O compilador implementado está totalmente funcional, como pode ser observado na \autoref{compiler}. O código de entrada pode ser observado em \autoref{codent} e o código gerado em \autoref{codgen}.


\begin{figure}[!h]%
\centering
\includegraphics[width=0.6\columnwidth]{compiler}%
\caption{Saída do compilador com a opção de verbose}%
\label{compiler}%
\end{figure}


\begin{lstlisting}[frame=single, framerule=0pt, caption={Código de entrada}, label=codent]
<nome>joao</nome>
<versao>1.1</versao>
<variavel> rightSensor 	0.0 </variavel>
<variavel> leftSensor 	0.0 </variavel>
<variavel> middleSensor 0.0 </variavel>
<variavel> leftMotorSpeed  0.0 </variavel>
<variavel> rightMotorSpeed 0.0 </variavel>
<variavel> proximitySensor 0.0 </variavel>
<variavel> semaphorePosition 0.0 </variavel>
<regras>
	<regra>
		<comandos>
			<comando>
				<leia_sensor>rightSensor</leia_sensor>				
			</comando>
			<comando>
				<leia_sensor>middleSensor</leia_sensor>				
			</comando>
			<comando>
				<leia_sensor>leftSensor</leia_sensor>				
			</comando>
			<comando>
				<leia_sensor>proximitySensor</leia_sensor>				
			</comando>
			<comando>
				<mensagem> <nome> semaforo </nome> semaphorePosition</mensagem>
			</comando>
		</comandos>	
	</regra>	
	<regra>
		<se>
			<condicao> 
				(middleSensor < 128.0) OR (rightSensor >= 128.0 AND (middleSensor >= 128.0
					AND leftSensor >= 128.0))
			</condicao>
		<entao>
			<comandos>
				<comando> leftMotorSpeed  <- (3.1415 * 1.5)</comando>	
				<comando> rightMotorSpeed <- (3.1415 * 1.5)</comando>			
			</comandos>			
		</se>
	</regra>
	<regra>
		<se>
			<condicao> 
				rightSensor < 128.0
			</condicao>
		<entao>
			<comandos>
				<comando> leftMotorSpeed  <- (3.1415 * 0.1)</comando>	
				<comando> rightMotorSpeed <- (3.1415 * -0.2)</comando>			
			</comandos>	
		</se>
	</regra>
	<regra>
		<se>
			<condicao> 
				leftSensor < 128.0
			</condicao>
		<entao>
			<comandos>
				<comando> leftMotorSpeed  <- (3.1415 * -0.2)</comando>	
				<comando> rightMotorSpeed <- (3.1415 * 0.1)</comando>			
			</comandos>			
		</se>
	</regra>
	<regra>
		<se>
			<condicao> 
				(proximitySensor > 0.0) AND (semaphorePosition == 0.0)
			</condicao>
		<entao>
			<comandos>
				<comando> leftMotorSpeed  <- 0.0</comando>	
				<comando> rightMotorSpeed <- 0.0</comando>	
				<comando> proximitySensor <- 0.0</comando>			
			</comandos>			
		</se>
	</regra>
	<regra>
		<comandos>
			<comando>
				<escreva_atuador>leftMotor leftMotorSpeed</escreva_atuador>				
			</comando>
			<comando>
				<escreva_atuador>rightMotor rightMotorSpeed</escreva_atuador>			
			</comando>			
		</comandos>	
	</regra>	
</regras>
\end{lstlisting}



\begin{lstlisting}[frame=single, framerule=0pt, caption={Código de saída}, label=codgen]
/* Generated by Agents Language Compiler */

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <cstdlib>
#include <stddef.h>
#include <string>
#include <boost\asio.hpp>
#include <boost\algorithm\string.hpp>
#include <Message.h>
#include <vector>
#include "AgentsLanguageAux.h"
using namespace AgentsLanguage;
using namespace std;
using boost::asio::ip::tcp;

/* Program Name */
string _program_name = "joao";
/* Program Version */
const double _program_version = 1.1;

/* Variables */
double rightSensor = 0;
double leftSensor = 0;
double middleSensor = 0;
double leftMotorSpeed = 0;
double rightMotorSpeed = 0;
double proximitySensor = 0;
double semaphorePosition = 0;

int main(int argc, char *argv[])
{
	int _portNumber = 0;
	int _leftMotorHandler = 0;
	int _rightMotorHandler = 0;
	int _proximitySensorHandler = 0;
	int _rightVisionSensorHandler = 0;
	int _middleVisionSensorHandler = 0;
	int _leftVisionSensorHandler = 0;
	if (argc >= 8)
	{
		_portNumber = atoi(argv[1]);
		_leftMotorHandler = atoi(argv[2]);
		_rightMotorHandler = atoi(argv[3]);
		_proximitySensorHandler = atoi(argv[4]);
		_rightVisionSensorHandler = atoi(argv[5]);
		_middleVisionSensorHandler = atoi(argv[6]);
		_leftVisionSensorHandler = atoi(argv[7]);
	}
	else
	{
		printf("Expecting following arguments: portNumber leftMotorHandler rightMotorHandler proximitySensorHandler rightVisionSensorHandler middleVisionSensorHandler leftVisionSensorHandler\n");
		return 0;
	}

	boost::asio::io_service ioService;
	tcp::resolver resolver(ioService);
	tcp::resolver::query query(tcp::v4(), "localhost", "1313");
	tcp::resolver::iterator iterator = resolver.resolve(query);
	tcp::socket s(ioService);
	boost::asio::connect(s, iterator);
	int _clientID = simxStart((simxChar*)"127.0.0.1", _portNumber, true, true, 2000, 5);
	if (_clientID != -1)
	{
		string msgAnyMessage = _program_name + " server";
		MessageHeader header(msgAnyMessage.length() + 5, MessageType::ANY_MESSAGE_FOR_ME);
		Message anyMessage(header, msgAnyMessage);
		string msgAnyMessageBuffer = anyMessage.GetMessageBuffer();
		while (simxGetConnectionId(_clientID) != -1)
		{
			//main loop
			/* begin user generated code */

			/* Rule */
			rightSensor = Aux::readVisionSensor(_clientID, _rightVisionSensorHandler);
			middleSensor = Aux::readVisionSensor(_clientID, _middleVisionSensorHandler);
			leftSensor = Aux::readVisionSensor(_clientID, _leftVisionSensorHandler);
			proximitySensor = Aux::readProximitySensor(_clientID, _proximitySensorHandler);
			string msgReqsemaforosemaphorePosition = _program_name + " semaforo semaphorePosition";
			MessageHeader headerReqsemaforosemaphorePosition(5 + msgReqsemaforosemaphorePosition.length(), MessageType::REQUEST_INFO);
			Message requestsemaforosemaphorePosition(headerReqsemaforosemaphorePosition, msgReqsemaforosemaphorePosition);
			string buffReqsemaforosemaphorePosition = requestsemaforosemaphorePosition.GetMessageBuffer();
			boost::asio::write(s, boost::asio::buffer(buffReqsemaforosemaphorePosition.c_str(), buffReqsemaforosemaphorePosition.length()));

			/* Rule */
			if (((middleSensor < 128)) || ((rightSensor >= 128) && ((middleSensor >= 128) && (leftSensor >= 128))))
			{
				leftMotorSpeed = (3.1415 * 1.5);
				rightMotorSpeed = (3.1415 * 1.5);
			}

			/* Rule */
			if ((rightSensor < 128))
			{
				leftMotorSpeed = (3.1415 * 0.1);
				rightMotorSpeed = (3.1415 * -0.2);
			}

			/* Rule */
			if ((leftSensor < 128))
			{
				leftMotorSpeed = (3.1415 * -0.2);
				rightMotorSpeed = (3.1415 * 0.1);
			}

			/* Rule */
			if (((proximitySensor > 0)) && ((semaphorePosition == 0)))
			{
				leftMotorSpeed = 0;
				rightMotorSpeed = 0;
				proximitySensor = 0;
			}

			/* Rule */
			Aux::setMotorTargetVelocity(_clientID, _leftMotorHandler, leftMotorSpeed);
			Aux::setMotorTargetVelocity(_clientID, _rightMotorHandler, rightMotorSpeed);
			/* end user generated code */

			boost::asio::write(s, boost::asio::buffer(msgAnyMessageBuffer.c_str(), msgAnyMessageBuffer.length()));
			vector<char> replyHeader(5);
			boost::asio::read(s, boost::asio::buffer(replyHeader));
			int messageLength = 0;
			messageLength |= replyHeader[0] << 24;
			messageLength |= replyHeader[1] << 16;
			messageLength |= replyHeader[2] << 8;
			messageLength |= replyHeader[3];
			int msgType = replyHeader[4];
			if (msgType != MessageType::NO_MESSAGES_FOR_YOU)
			{
				vector<char> replyMessage(messageLength - replyHeader.size());
				boost::asio::read(s, boost::asio::buffer(replyMessage));
				string strMsg(replyMessage.data(), replyMessage.size());
				vector<string> subStrings;
				boost::split(subStrings, strMsg, boost::is_any_of(" "));
				if (msgType == MessageType::SEND_INFO)
				{
					string varName = subStrings[2];
					if (varName == "semaphorePosition")
					{
						semaphorePosition = atof(subStrings[3].c_str());
					}
				}
			}

			extApi_sleepMs(5);
		}
		simxFinish(_clientID);
	}


	return 0;
}
\end{lstlisting}


O código gerado deve ser adicionado ao Projeto C++ chamado \texttt{RobotClient} para que seja compilado. No arquivo \texttt{AgentsLanguageAux.h} estão definidas as funções de leitura e escrita dos sensores e atuadores. Caso seja necessário alterar tais rotinas, basta alterá-las neste arquivo e no gerador de código do compilador, onde é gerado o código que chama tais funções.

\section{Integração com Simulador V-REP}

A \autoref{scene} mostra o simulador com os dois robôs seguidores de linha e o semáforo.

\begin{figure}[!h]%
\centering
\includegraphics[width=\columnwidth]{scene}%
\caption{Cena montada no simulador V-REP}%
\label{scene}%
\end{figure}

A \autoref{message-server} mostra a troca de mensagens entre os robôs seguidores de linha e o semáforo através do servidor de mensagens.

\begin{figure}[!h]%
\centering
\includegraphics[width=\columnwidth]{server}%
\caption{Servidor de Mensagens}%
\label{message-server}%
\end{figure}



\chapter{Conclusões}

Através deste trabalho foi possível colocar em prática toda a teoria que foi aprendida em sala de aula. Aprendeu-se ainda todos os passos de produção de um compilador. Os objetivos propostos foram atingidos, na medida em que foram obtidos resultados expressivos. 

Como sugestão para trabalhos futuros fica a alteração e a inserção de novas regras gramaticais para que possibilite uma indenpendência maior do tipo de robô utilizado e uma implementação mais eficiente da troca de mensagens.

\bibliography{agents}
\end{document}